#include <iostream>
#include <algorithm>
#include <functional>
#include <ctime>
#include <vector>
using namespace std;
//
//template<typename T>
//auto drawOutRandItem(const T& container, std::function<int(decltype(&(*std::begin(container))))> get_draw_item_weight) ->\
//	decltype(&(*std::begin(container)))
//{
//	int total_weight = 0;
//	for (const auto& item : container)	total_weight += get_draw_item_weight(&item);
//
//	if (total_weight <= 0)	return nullptr;
//
//	//获取随机值
//	srand(time(0));
//
//	int random_number = rand() % total_weight;
//
//	for (const auto& item : container)
//	{
//		if (get_draw_item_weight(&item) >= random_number)
//		{
//			return &item;
//			break;
//		}
//
//		random_number -= get_draw_item_weight(&item);
//	}
//	
//	return nullptr;
//}
//
//struct DrawItem
//{
//	int item_id;
//	int weight;
//};
//
//int main()
//{
//	//
//
//	std::vector<DrawItem> item_pool(10);
//	for (size_t i = 0; i < item_pool.size(); ++i)
//	{
//		item_pool[i].item_id = static_cast<int>(i + 1000);
//		item_pool[i].weight = static_cast<int>(1 + rand() % 95);
//	}
//
//	const DrawItem* item = drawOutRandItem(item_pool, [](const DrawItem* item){
//		return item->weight;
//	});
//
//	cout << item->item_id << endl;
//	return 0;
//}

//alias method
#include <iostream>
#include <queue>
#include <vector>
#include <random>
#include <ctime>
#include <functional>

#define BASE_PER 100

struct DrawItem
{
	int item_id;
	int weight;
};

template<typename T>
const T* drawOutRandItem(std::vector<T>& box, std::function<int(const T*)> get_item_weight)
{
	const int len = box.size();
	std::vector<int> alias(len, 0);
	std::queue<int> big, small;

	//计算总权重
	int total_weight = 0;
	for (int i = 0; i < len; ++i) total_weight += get_item_weight(&box[i]);
	if (total_weight <= 0)	return nullptr;
	
	//生成第一个逻辑
	for (int i = 0; i < len; ++i)
	{
		int change_weight = get_item_weight(&box[i]) * len;
		alias[i] = change_weight;

		if (change_weight > total_weight)	big.push(i);
		else if (change_weight < total_weight)	small.push(i);
	}

	//处理
	while (!big.empty() && !small.empty())
	{
		int big_idx = big.front(); big.pop();
		int small_idx = small.front(); small.pop();

		//填补
		alias[big_idx] -= total_weight - alias[small_idx];
		alias[small_idx] = big_idx;

		if (alias[big_idx] < total_weight) small.push(big_idx);
	}

	for (int i = 0; i < len; ++i)
	{
		if (alias[i] >= total_weight)	alias[i] = i;
	}

	srand(time(0));

	//rand第一次判断是那个下标 box&alias[first_rand];
	int first_rand = rand() % len;

	//rand第二次判断是下表里面的哪个部分
	int second_rand = rand() % BASE_PER;
	
	if (second_rand > get_item_weight(&box[first_rand]))
		return &(box[alias[first_rand]]);
	return &(box[first_rand]);
}

int main()
{
	//

	std::vector<DrawItem> item_pool(10);
	for (size_t i = 0; i < item_pool.size(); ++i)
	{
		item_pool[i].item_id = static_cast<int>(i + 1000);
		item_pool[i].weight = 50;
	}

	for (int i = 0; i < 10000; ++i)
	{
		const DrawItem* item = drawOutRandItem<DrawItem>(item_pool, [](const DrawItem* item) {
			return item->weight;
			});

		cout << item->item_id << endl;
	}
	return 0;
}